import sun.font.EAttribute;

import javax.print.attribute.HashPrintRequestAttributeSet;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName Code01_ReverseList
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/12/13 12:22
 */
public class Code01_ReverseList {

    // 单链表结点
    public static class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    // 双链表结点
    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int value) {
            this.value = value;
        }
    }

    // 翻转链单表
    /*public static Node reverseLinkedList(Node head) {
        Node prev = null;
        Node cur = head;
        while (cur != null) {
            Node next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }*/

    public static Node reverseLinkedList(Node head) {
        Node prev = null;
        while (head != null) {
            Node next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    // 测试翻转单链表
    public static Node testReverseLinkedList(Node head) {
        if (head == null) {
            return null;
        }
        LinkedList<Node> list = new LinkedList<>();
        Node prev = null;
        while (head != null) {
            Node next = head.next;
            list.addFirst(head);
            list.get(0).next = prev;
            prev = list.get(0);
            head = next;
        }
        return list.get(0);
    }

    public static Node testReverseLinkedList2(Node head) {
        if (head == null) {
            return null;
        }
        ArrayList<Node> arrayList = new ArrayList<>();
        while (head != null) {
            arrayList.add(head);
            head = head.next;
        }
        arrayList.get(0).next = null;
        int len = arrayList.size();
        for (int i = 1; i < len; i++) {
            arrayList.get(i).next = arrayList.get(i - 1);
        }
        return arrayList.get(len - 1);
    }

    // 翻转双链表
    /*public static DoubleNode reverseDoubleList(DoubleNode head) {
        DoubleNode prev = null;
        DoubleNode cur = head;
        while (cur != null) {
            DoubleNode next = cur.next;
            cur.next = prev;
            cur.last = next;
            prev = cur;
            cur = next;
        }
        return prev;
    }*/
    public static DoubleNode reverseDoubleList(DoubleNode head) {
        DoubleNode prev = null;
        while (head != null) {
            DoubleNode next = head.next;
            head.next = prev;
            head.last = next;
            prev = head;
            head = next;
        }
        return prev;
    }

    // 测试翻转双链表
    public static DoubleNode testReverseDoubleList(DoubleNode head) {
        if (head == null) {
            return null;
        }
        LinkedList<DoubleNode> list = new LinkedList<>();
        DoubleNode prev = null;
        while (head != null) {
            DoubleNode next = head.next;
            list.addFirst(head);
            list.get(0).next = prev;
            list.get(0).last = next;
            prev = head;
            head = next;
        }
        return list.get(0);
    }

    public static DoubleNode testReverseDoubleList2(DoubleNode head) {
        if (head == null) {
            return null;
        }
        ArrayList<DoubleNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        list.get(0).next = null;
        DoubleNode prev = list.get(0);
        int len = list.size();
        for (int i = 1; i < len; i++) {
            DoubleNode cur = list.get(i);
            cur.next = prev;
            prev.last = cur;
            prev = cur;
        }
        prev.last = null;
        return list.get(len - 1);
    }

    public static DoubleNode testReverseDoubleList3(DoubleNode head) {
        if (head == null) {
            return null;
        }
        ArrayList<DoubleNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        list.get(0).next = null;
        DoubleNode prev = list.get(0);
        int len = list.size();
        for (int i = 1; i < len; i++) {
            DoubleNode cur = list.get(i);
            // 不知道cur的上一个还有没有，没有了的话就是头结点了
            cur.last = null;
            cur.next = prev;
            prev.last = cur;
            prev = cur;
        }
        return list.get(len - 1);
    }

    // 生成随机单链表
    public static Node generateRandomLinkedList(int len, int value) {
        int size = (int) (Math.random() * (len + 1));
        if (size == 0) {
            return null;
        }
        Node head = new Node((int) (Math.random() * (value + 1)));
        Node pre = head;
        while (size - 1 != 0) {
            Node cur = new Node((int) (Math.random() * (value + 1)));
            pre.next = cur;
            pre = cur;
            size--;
        }
        return head;
    }

    // 获取链表原始值顺序
    public static List<Integer> getLinkedListOriginOrder(Node head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.value);
            head = head.next;
        }
        return list;
    }

    // 检测单链表翻转是否成功
    public static boolean checkLinkedListReverse(List<Integer> origin, Node head) {
        for (int i = origin.size() - 1; i >= 0; i--) {
            if (!origin.get(i).equals(head.value)) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    // 随机生成双链表
    public static DoubleNode generateRandomDoubleList(int len, int value) {
        int size = (int) (Math.random() * (len + 1));
        if (size == 0) {
            return null;
        }
        DoubleNode head = new DoubleNode((int) (Math.random() * (value + 1)));
        DoubleNode pre = head;
        while (size - 1 != 0) {
            DoubleNode cur = new DoubleNode((int) (Math.random() * (value + 1)));
            pre.next = cur;
            cur.last = pre;
            pre = cur;
            size--;
        }
        return head;
    }

    // 获取双链表原始值顺序
    public static List<Integer> getDoubleListOriginOrder(DoubleNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.value);
            head = head.next;
        }
        return list;
    }

    // 检测双链表翻转是否成功
    public static boolean checkDoubleListReverse(List<Integer> origin, DoubleNode head) {
        // 从后往前是不是翻转的
        DoubleNode end = null;
        for (int i = origin.size() - 1; i >= 0; i--) {
            if (!origin.get(i).equals(head.value)) {
                return false;
            }
            end = head;
            head = head.next;
        }
        // 从前往后是不是翻转的
        for (int i = 0; i < origin.size(); i++) {
            if (!origin.get(i).equals(end.value)) {
                return false;
            }
            end = end.last;
        }
        return true;
    }

    // 打印单链表
    public static void printLinkedList(Node head) {
        while (head != null) {
            System.out.print(head.value +  " ");
            head = head.next;
        }
        System.out.println();
    }

    // 打印双链表
    public static void printDoubleList(DoubleNode head) {
        while (head != null) {
            System.out.print(head.value +  " ");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int len = 50;
        int value = 100;
        int testTimes = 10000;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomLinkedList(len, value);
            List<Integer> origin = getLinkedListOriginOrder(head);
            Node reverse = reverseLinkedList(head);
            boolean flag1 = checkLinkedListReverse(origin, reverse);
            if (!flag1) {
                System.out.println("LinkedList测试异常！");
                System.out.print("originLinkedList：");
                printLinkedList(head);
                System.out.print("reverseLinkedList：");
                printLinkedList(reverse);
            }

            Node headTest = generateRandomLinkedList(len, value);
            List<Integer> originTest = getLinkedListOriginOrder(headTest);
            Node reverseTest = testReverseLinkedList(headTest);
            boolean flagTest1 = checkLinkedListReverse(originTest, reverseTest);
            if (!flagTest1) {
                System.out.println("LinkedList测试异常！");
                System.out.print("originLinkedList：");
                printLinkedList(headTest);
                System.out.print("reverseLinkedList：");
                printLinkedList(reverseTest);
            }

            DoubleNode headDouble = generateRandomDoubleList(len,value);
            List<Integer> originDouble = getDoubleListOriginOrder(headDouble);
            DoubleNode reverseDouble = reverseDoubleList(headDouble);
            boolean flag2 = checkDoubleListReverse(originDouble,reverseDouble);
            if (!flag2) {
                System.out.println("DoubleList测试异常！");
                System.out.print("originDoubleList：");
                printDoubleList(headDouble);
                System.out.print("reverseDoubleList：");
                printDoubleList(reverseDouble);
            }

            DoubleNode headDoubleTest = generateRandomDoubleList(len,value);
            List<Integer> originDoubleTest = getDoubleListOriginOrder(headDoubleTest);
            DoubleNode reverseDoubleTest = testReverseDoubleList(headDoubleTest);
            boolean flagTest2 = checkDoubleListReverse(originDoubleTest,reverseDoubleTest);
            if (!flagTest2) {
                System.out.println("DoubleList测试异常！");
                System.out.print("originDoubleList：");
                printDoubleList(headDoubleTest);
                System.out.print("reverseDoubleList：");
                printDoubleList(reverseDoubleTest);
            }

            if (!flag1 || !flag2 || !flagTest1 || !flagTest2) {
                System.out.println("测试异常退出程序！");
                break;
            }
        }
        System.out.println("测试结束");
    }
}
